#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>

#define SIZE_TAB 4

void fusion(int tableau[], int deb1, int fin1, int fin2);
void tri_fusion_bis(int tableau[], int deb, int fin, int count);
void tri_fusion(int tableau[], int longueur);

int main(){
	int tab[] = {8,3,1,6,2};
	tri_fusion(tab, 5);
	return 0;
}

/*
 *  
 */
void affiche_tab(int * tab){
	int i;

	for(i=0; i <= SIZE_TAB ; i++) {
		printf ("[%d] %d ", i, tab[i]);
	}
}

/*
 *
 */
void fusion(int tableau[], int deb1, int fin1, int fin2){
        int *table1;
        int deb2=fin1+1;
        int compt1=deb1;
        int compt2=deb2;
        int i;

	printf (" [deb fusion]  -->   " );
	affiche_tab(tableau ) ;
	printf (" \n");

	table1 = malloc((fin1-deb1+1)*sizeof(int));

	//on recopie les elements du debut du tableau
        for(i=deb1;i<=fin1;i++){
            table1[i-deb1]=tableau[i];
        }

	printf (" cpy tableau \n");

        for(i=deb1;i<=fin2;i++) {
		printf ("Elements  %d  \n",i);

		if (compt1==deb2) {
			printf ("  tous les elements sont classes  \n");
			break;
		}
            	else if (compt2==(fin2+1)){
	               	tableau[i]=table1[compt1-deb1]; 
              		compt1++;
                }
            	else if (table1[compt1-deb1]<tableau[compt2]){
                	tableau[i]=table1[compt1-deb1]; 
                	compt1++;
                }
            	else {
                	tableau[i]=tableau[compt2];
                	compt2++;
       		}
	}

        free(table1);
	printf (" [fin fusion]  -->   " ); 
        affiche_tab(tableau ) ;
	printf (" \n");
}

/*
 *
 */
void tri_fusion_bis(int tableau[],int deb,int fin,int count ) {
	sleep(1);
	printf ("[%d]  Iteration debut %d fin %d \n", count, deb , fin ) ;
        if (deb!=fin){
		int milieu=(fin+deb)/2;
            	tri_fusion_bis(tableau,deb,milieu,count+1);
            	tri_fusion_bis(tableau,milieu+1,fin,count+1);
            	fusion(tableau,deb,milieu,fin);
    	}
}

/*
 *
 */
void tri_fusion(int tableau[],int longueur){
	if (longueur>0){
            	tri_fusion_bis(tableau,0,longueur-1,-1);
    	}
}
